This invention relates to an operation apparatus, an operation method for calculating a remainder, and a recording medium thereof. In particular, the invention relates to an operation apparatus, an operation method for calculating a remainder using a computer, and a recording medium thereof.
Related Art 1.
In the following, as the first conventional related art, an example of the conventional technique, where a remainder operating method disclosed in U.S. Pat. No. 5,463,690 is applied, will be explained referring to FIG. 15. This relates to an operation method for calculating a remainder of an integer Z divided by a prime number P. Here, it is assumed that the prime number P is limited to be a number which can be represented by 2qxe2x88x92C (q: a natural number; C: a relatively small odd number). By limiting the prime number as the above, the remainder can be calculated using only shift operation, addition and subtraction. Here, the calculation of remainder is performed by a computer having 2M as a basic operational unit.
For example, as shown in FIG. 15, the remainder of the integer 685 divided by the prime number 13 (q=4, C=3) can be calculated using the computer having 23 (3 bits) as the basic operational unit, and the operation will be described in the following:
When represented by binary number, 685 becomes (1010101101).
First, the lowest bits q=4 bits 1401 (1101) of the integer Z=685 are latched. Next, data 1403 (1111110), which is the remaining bits 1402 (101010) multiplied by C=3, is calculated by shift operation and addition. Then, the obtained data 1403 is added to the data 1401 (1101) to obtain data 1404 (10001011).
Then, the lowest bits q=4 bits 1405 (1011) of the data 1404 are latched. Subsequently, data 1407 (11000), which is the remaining bits 1406 (1000) multiplied by C=3, is calculated by shift operation and addition. Further, the data 1407 is added to the data 1405 to produce data 1408 (100011).
Then, the lowest bits q=4 bits 1409 (0011) of the obtained data 1408 are latched. Subsequently, data 1411 (110), which is the remaining bits 1410 (10) multiplied by C=3, is calculated by shift operation and addition. Further, the data 1411 is added to the data 1409 to produce data 1412 (10001).
The data 1412 includes q bits where q is q=4 or q=less than 4, and is a remainder of the integer Z divided by the prime number P. Namely, (1001)=9, and the remainder 9 of 685 divided by 13 is obtained.
Related Art 2.
In the following, as the second conventional related art, an operating method for calculating a remainder R of a division of an integer Z by an integer I will be explained referring to FIG. 16. The operating method is considered basically in the same way as the first related art, however, the concrete number used therein is different from the first related art. The operating method implemented by the 16-bit computer will be explained, and the operation is performed with 16 bits as a processing unit. In FIG. 16, a reference numeral 1501 shows an integer Z, 1502 shows an integer I (I=2160 +ff9d), 1503 shows higher 64 bit data Zh of the integer Z, 1504 shows lower 160 bit data Zl of the integer Z, and 1509 shows a remainder R. In FIG. 16, the integer Z and the remainder R are represented by hexadecimal numbers, and in the integer I, 2160 is represented by decimal number, ff9d by hexadecimal number.
The highest 16 bits of I are 1, and the remainder can be calculated by subtracting Zh 1503 multiplied by ff9d from Zl 1504. Concretely, the following process is used for calculating the remainder.
First, the lowest 16 bit data aaaa of Zh 1503 is multiplied by ff9d to obtain 32 bit data aa680042 (1505) (multiplication 1). Next, bbbb is multiplied by ff9d to obtain 32 bit data bb7266af (1506) (multiplication 2). Subsequently, cccc is multiplied by ff9d to obtain 32 bit data cc7ccd1c (1507) (multiplication 3).
Then, dddd is multiplied by ff9d to obtain 32 bit data dd873389 (1508) (multiplication 4). Through the above 4 multiplications, a product of multiplication of Zh and ff9d is obtained.
Subsequently, this product is subtracted from Zl (1504). In the following, addition and subtraction include carry and borrow.
First, 0042 is subtracted from the lowest 16 bit data 0000 of Zl (1504) (addition/subtraction 1). Next, aa68 is subtracted from 1111 (addition/subtraction 2), and further 66af is subtracted (addition/subtraction 3). Subsequently, bb72 is subtracted from 2222 (addition/subtraction 4), and further cd1c is subtracted (addition/subtraction 5). Then, cc7s is subtracted from 3333 (addition/subtraction 6), and further 3389 is subtracted (addition/subtraction 7). Finally, dd87 is subtracted from 4444 (addition/subtraction 8).
As has been described, the remainder R 1509 of the integer Z divided by the integer I is calculated through 4 multiplications and 8 additions/subtractions.
In the above related arts, when the prime number P is 2qxe2x88x92C (C is a relatively small odd number), the remainder can be calculated without division, which allows the operation proceed quickly. However, even if the calculation excludes the division, the calculation includes the shift operation, which limits the operating speed of the calculation.
Further, as clearly described in the second related art, when the integer I is 2qxe2x88x92f (q=4, f=3 in the first related art, q=160, f=ff9d in the second related art), f (3 or ff9d) multiplication steps are required. And the multiplication result exceeds 16 bits of the basic operation unit, so that the number of accompanied additions or subtractions becomes large. Consequently, the code size becomes large, and when the number of processing steps is large, the operation may delay.
The present invention is provided to solve the above-mentioned problems, and aims to obtain an operation apparatus, operation method for calculating the remainder of the integer at a high speed using a computer and recording medium thereof
An operation apparatus in relation to the present invention for calculating a remainder R of data Z having Bz bits divided by data I represented by a following equation:   I  =            ∑              N        =        0                    N        =                  N          max                      ⁢          xe2x80x83        ⁢                  A        N            ⁢              Q        MN            
(M is a number of bits of a basic operational unit; N is a natural number being one of 0 through Nmax, A0 is a value whose absolute value is smaller than a value represented by the basic operational unit of M bits; each of A1 through ANmaxxe2x88x921 is +1, 0, or xe2x88x921; ANmax is +1, or xe2x88x921; and Q is a natural number equal to or more than 2) the operation apparatus includes:
(1) a data Zl storing region for storing data Zl of lower Mxc3x97Nmax bits of the data Z;
(2) a data Zh storing region for storing data Zh of higher (Bzxe2x88x92Mxc3x97Nmax) bits of the data Z;
(3) a data AN storing region for storing the data AN; and
(4) an addition/subtraction unit for calculating the remainder R by determining an operation between addition and subtraction based on positive/negative of the data AN, and operating addition/subtraction of data stored in at least a part of the data Zl storing region and data stored in at least a part of the data Zh storing region.
Further, in the operation apparatus, the data Zl storing region stores the data Zl as data Zl(i) divided by the basic operational unit of M bits sequentially from a lowest side within a range of a natural number i (1xe2x89xa6ixe2x89xa6Nmax) in a data Zl(i) region;
the data Zh storing region stores the data Zh as data Zh(j) divided by the basic operational unit of M bits sequentially from a lowest side within a range of a natural number j (a natural number of 1xe2x89xa6jxe2x89xa6(Bz/M)xe2x88x92Nmax with raising its decimals) in a data Zh(j) region; and
the addition/subtraction unit determines the operation between addition and subtraction using N having a predetermined relationship with i and j, and operates addition/subtraction of the data Zl(i) and the data Zh(j).
Further, in the operation apparatus, the addition/subtraction unit determines the operation using N having a relationship of N=ixe2x88x92j that the operation is subtraction when the data AN is positive, and that the operation is addition when the data AN is negative.
Further, in the operation apparatus, the addition/subtraction unit continuously operates addition/subtraction for pairs of i and j having a relationship of N=ixe2x88x92j against a certain N.
Further, in the operation apparatus, the addition/subtraction unit continuously operates addition/subtraction for pairs of N and j having a relationship of N=ixe2x88x92j against a certain i.
An operation method in relation to the present invention, using an operation apparatus, for calculating a remainder R of data Z having Bz bits divided by data I represented by a following equation:   I  =            ∑              N        =        0                    N        =                  N          max                      ⁢          xe2x80x83        ⁢                  A        N            ⁢              Q        MN            
(M is a number of bits of a basic operational unit; N is a natural number being one of 0 through Nmax, A0 is a value whose absolute value is smaller than a value represented by the basic operational unit of M bits; each of A1 through ANmaxxe2x88x921 is +1, 0, or xe2x88x921; ANmax is +1, or xe2x88x921; and Q is a natural number equal to or more than 2) the operation method includes:
(1) a data Zl storing step of storing data Zl of lower Mxc3x97Nmax bits of the data Z;
(2) a data Zh storing step of storing data Zh of higher (Bzxe2x88x92Mxc3x97Nmax) bits of the data Z;
(3) a data AN storing step of storing the data AN; and
(4) an adding/subtracting step of calculating the remainder R by determining an operation between addition and subtraction based on positive/negative of the data AN, and operating addition/subtraction of data stored in at least a part of the data Zl storing region and data stored in at least a part of the data Zh storing region.
Further, in the operation method, the data Zl storing step stores the data Zl as data Zl(i) divided by the basic operational unit of M bits sequentially from a lowest side within a range of a natural number i (1xe2x89xa6ixe2x89xa6Nmax);
the data Zh storing step stores the data Zh as data Zh(j) divided by the basic operational unit of M bits sequentially from a lowest side within a range of a natural number j (a natural number of 1xe2x89xa6jxe2x89xa6(Bz/M)xe2x88x92Nmax with raising its decimals); and
the adding/subtracting step determines the operation between addition and subtraction using N having a predetermined relationship with i and j, and operates addition/subtraction of the data Zl(i) and the data Zh(j).
In a computer readable recording medium in relation to the present invention having a computer readable program stored therein for causing a computer to perform an operation process using an operation apparatus for calculating a remainder R of data Z having Bz bits divided by data I represented by a following equation:   I  =            ∑              N        =        0                    N        =                  N          max                      ⁢          xe2x80x83        ⁢                  A        N            ⁢              Q        MN            
(M is a number of bits of a basic operational unit; N is a natural number being one of 0 through Nmax, A0 is a value whose absolute value is smaller than a value represented by the basic operational unit of M bits; each of A1 through ANmaxxe2x88x921 is +1, 0, or xe2x88x921; ANmax is +1, or xe2x88x921; and Q is a natural number equal to or more than 2) the operation process includes:
(1) a data Zl storing process for storing data Zl of lower Mxc3x97Nmax bits of the data Z;
(2) a data Zh storing process for storing data Zh of higher (Bzxe2x88x92Mxc3x97Nmax) bits of the data Z;
(3) a data AN storing process for storing the data AN; and
(4) an adding/subtracting process for calculating the remainder R by determining an operation between addition and subtraction based on positive/negative of the data AN, and operating addition/subtraction of data stored in at least a part of the data Zl storing region and data stored in at least a part of the data Zh storing region.
Further, in the computer readable recording medium, the data Zl storing process stores the data Zl as data Zl(i) divided by the basic operational unit of M bits sequentially from a lowest side within a range of a natural number i (1xe2x89xa6ixe2x89xa6Nmax);
the data Zh storing process stores the data Zh as data Zh(j) divided by the basic operational unit of M bits sequentially from a lowest side within a range of a natural number j (a natural number of 1xe2x89xa6jxe2x89xa6(Bz/M)xe2x88x92Nmax with raising its decimals); and
the additing/subtracting process determines the operation between addition and subtraction using N having a predetermined relationship with i and j, and operates addition/subtraction of the data Zl(i) and the data Zh(j).
An operation apparatus in relation to the invention for calculating a remainder R of data Z having Bz bits divided by data I represented by a following equation:
I=CQnxc2x11 
(M is a number of bits of a basic operational unit; Q is a natural number equal to or more than 2; n is nxe2x89xa7M; and C is 1 less than C less than QM) the operation apparatus includes:
(1) a data Zl storing region for storing data Zl of lower n bits of the data Z;
(2) a data Zh storing region for storing data Zh of higher Bzxe2x88x92n bits of the data Z;
(3) a quotient calculating unit for calculating a quotient q and a remainder r by dividing the data Zh with the data C; and
(4) an addition/subtraction unit for calculating the remainder R by adding the remainder r as a basic operational unit higher than the data Zl to the data Zl, and adding/subtracting the quotient q to/from an added result.
An operation method in relation to the present invention, using an operation apparatus, for calculating a remainder R of data Z having Bz bits divided by data I represented by a following equation:
I=CQnxc2x11 
(M is a number of bits of a basic operational unit; Q is a natural number equal to or more than 2; n is nxe2x89xa7M; and C is 1 less than C less than QM) the operation method includes:
(1) a data Zl storing step of storing data Zl of lower n bits of the data Z;
(2) a data Zh storing step of storing data Zh of higher Bzxe2x88x92n bits of the data Z;
(3) a quotient calculating step of calculating a quotient q and a remainder r by dividing the data Zh with the data C; and
(4) an adding/subtracting step of calculating the remainder R by adding the remainder r as a basic operational unit higher than the data Zl to the data Zl, and adding/subtracting the quotient q to/from an added result.
In a computer readable recording medium in relation to the invention having a computer readable program stored therein for causing a computer to perform an operation process using an operation apparatus for calculating a remainder R of data Z having Bz bits divided by data I represented by a following equation:
I=CQnxc2x11 
(M is a number of bits of a basic operational unit; Q is a natural number equal to or more than 2; n is nxe2x89xa7M; and C is 1 less than C less than QM) the operation process includes:
(1) a data Zl storing process for storing data Zl of lower n bits of the data Z;
(2) a data Zh storing process for storing data Zh of higher Bzxe2x88x92-n bits of the data Z;
(3) a quotient calculating process for calculating a quotient q and a remainder r by dividing the data Zh with the data C; and
(4) an adding/subtracting process for calculating the remainder R by adding the remainder r as a basic operational unit higher than the data Zl to the data Zl, and adding/subtracting the quotient q to/from an added result.
An operation apparatus in relation to the present invention for calculating a remainder R of data Z divided by data P includes a data I judging unit for judging if the data P equals a predetermined data I.
Further, in the operation apparatus, the predetermined data I of the data I judging unit is represented by a following equation:   I  =            ∑              N        =        0                    N        =                  N          max                      ⁢          xe2x80x83        ⁢                  A        N            ⁢              Q        MN            
(M is a number of bits of a basic operational unit; N is a natural number being one of 0 through Nmax, A0 is a value whose absolute value is smaller than a value represented by the basic operational unit of M bits; each of A1 through ANmaxxe2x88x921 is +1, 0, or xe2x88x921; ANmax is +1, or xe2x88x921; and Q is a natural number equal to or more than 2)
Further, in the operation apparatus, the predetermined data I of the data I judging unit is represented by a following equation:
I=CQnxc2x11 
(M is a number of bits of a basic operational unit; Q is a natural number equal to or more than 2; n is nxe2x89xa7M and C is 1 less than C less than QM)
An operation method in relation to the present invention for calculating a remainder R of data Z divided by data P includes a data I judging step of judging if the data P equals a predetermined data I.
Further, in the operation method, the predetermined data I of the data I judging unit is represented by a following equation:   I  =            ∑              N        =        0                    N        =                  N          max                      ⁢          xe2x80x83        ⁢                  A        N            ⁢              Q        MN            
(M is a number of bits of a basic operational unit; N is a natural number being one of 0 through Nmax, A0 is a value whose absolute value is smaller than a value represented by the basic operational unit of M bits; each of A1 through ANmaxxe2x88x921 is +1, 0, or xe2x88x921; ANmax is +1, or xe2x88x921; and Q is a natural number equal to or more than 2)
Further, in the operation method, the predetermined data I of the data I judging unit is represented by a following equation:
I=CQnxc2x11 
(M is a number of bits of a basic operational unit; Q is a natural number equal to or more than 2; n is nxe2x89xa7M; and C is 1 less than C less than QM)
In a computer readable recording medium in relation to the present invention having a computer readable program stored therein for causing a computer to perform an operation process using an operation apparatus for calculating a remainder R of data Z divided by data P, the operation process includes a data I judging process for judging if the data P equals to a predetermined data I.
Further, in the computer readable recording medium, the predetermined data I of the data I judging process is represented by a following equation:   I  =            ∑              N        =        0                    N        =                  N          max                      ⁢          xe2x80x83        ⁢                  A        N            ⁢              Q        MN            
(M is a number of bits of a basic operational unit; N is a natural number being one of 0 through Nmax, A0 is a value whose absolute value is smaller than a value represented by the basic operational unit of M bits; each of A1 through ANmaxxe2x88x921 is +1, 0, or xe2x88x921; ANmax is +1, or xe2x88x921; and Q is a natural number equal to or more than 2)
Further, in the computer readable recording medium, the predetermined data I of the data I judging process is represented by a following equation:
I=CQnxc2x11 
(M is a number of bits of a basic operational unit; Q is a natural number equal to or more than 2; n is nxe2x89xa7M; and C is 1 less than C less than QM)